/**
 * https://leetcode-cn.com/problems/merge-sorted-array/
 * 给你两个按非递减顺序排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
 * 请你合并nums2到nums1中，使合并后的数组同样按 非递减顺序 排列。
 *
 * 注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。
 * 为了应对这种情况，nums1的初始长度为 m + n，
 * 其中前m个元素表示应合并的元素，后n个元素为0，应忽略。nums2的长度为n。
 *
 * @Date 2021-11-13
 * @author X.
 *
 * Solution:
 * 这个题目跟合并两个有序链表还不太一样，因为数组是固定长度的，并且要求合并到num1上。
 * 因此如果从头逐一比较，那么nums1将需要做很多的元素位置变换。
 * 由于数组是固定长度和固定位置，因此考虑倒一头，倒着比较，从数组末尾开始比较，这样可以按序插入到nums1中
 * nums1中间需要移动的位置就会少很多。
 *
 * 中间有两个地方没有考虑到：
 * 1. while排序完之后，还要考虑，如果nums2中还有没有参与过比较的元素，
 * 那么说明这部分元素都小于nums1中的最小元素，此时应该将nums2的这部分元素覆盖到nums1的前面。
 * 2. 如果nums2的元素参与了比较，但是由于更小没有被放到nums1的末尾，
 * 那么此时应该将该元素先覆盖到末尾-1的位置上，再参与后续的比较
 *
 *
 * 倒序双指针
 * 时间复杂度O(m+n)，空间复杂度O(1)
 *
 * Solution2：
 * 时间复杂度：O((m+n)log(m+n))。
 * 排序序列长度为 m+n，套用快速排序的时间复杂度即可，平均情况为 O((m+n)log(m+n))。
 *
 * 空间复杂度：O(log(m+n))。
 * 排序序列长度为 m+n，套用快速排序的空间复杂度即可，平均情况为 O(log(m+n))。
 *
 */
public class MergeTwoArray88 {

    public void merge(int[] nums1, int m, int[] nums2, int n) {
        if (m == 0 && n == 0) {
            return;
        }
        if (m == 0) {
            for (int i = 0; i < n; i++) {
                nums1[i] = nums2[i];
            }
            return;
        }
        if (n == 0) {
            return;
        }
        int i = m-1;
        int j = n-1;
        while(i >= 0 && j >= 0) {
            if (nums1[i] < nums2[j]) {
                nums1[i+j+1] = nums2[j];
                j--;
            } else {
                nums1[i+j+1] = nums1[i];
                // 小的元素往前放一位
                nums1[i+j] = nums2[j];
                i--;
            }
        }
        // 还需要处理一下剩余的nums2中没参与比较的元素
        if (j > 0) {
            for (int x = 0; x <= j; x++) {
                nums1[x] = nums2[x];
            }
        }
    }

    public static void main(String[] args) {
        int[] nums1 = {4,5,6,0,0,0};
        int m = 3;
        int[] nums2 = {1,2,3};
        int n = 3;
//        merge(nums1, m, nums2, n);
    }
}


// Solution1的官方写法
public void merge(int[] nums1, int m, int[] nums2, int n) {
    int p1 = m - 1, p2 = n - 1;
    int tail = m + n - 1;
    int cur;
    while (p1 >= 0 || p2 >= 0) {
        if (p1 == -1) {
            cur = nums2[p2--];
        } else if (p2 == -1) {
            cur = nums1[p1--];
        } else if (nums1[p1] > nums2[p2]) {
            cur = nums1[p1--];
        } else {
            cur = nums2[p2--];
        }
        nums1[tail--] = cur;
    }
}

Solution2 - 直接合并后排序
public void merge(int[] nums1, int m, int[] nums2, int n) {
    for (int i = 0; i < n; i++) {
        nums1[m + i] = nums2[i];
    }
    Arrays.sort(nums1);
}